package main

import (
	"fmt"
)

/*
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
*/

func main() {
	fmt.Println(collectRain([]int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}))
}

func collectRain(height []int) int {
	n := len(height)
	leftMax := make([]int, n)
	rightMax := make([]int, n)
	for i := 0; i < n; i++ {
		if i == 0 {
			leftMax[i] = height[i]
			continue
		}
		leftMax[i] = max(leftMax[i-1], height[i])
	}
	for i := n - 1; i >= 0; i-- {
		if i == n-1 {
			rightMax[i] = height[i]
			continue
		}
		rightMax[i] = max(rightMax[i+1], height[i])
	}
	res := 0
	for i := 0; i < n; i++ {
		res += min(leftMax[i], rightMax[i]) - height[i]
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
